

In [ ]:

    
%%HTML
<style>
.container { width:100% }
</style>

Best First Search

The module heapq provides priority queues that are implemented as heaps. Technically, these heaps are just lists. In order to use them as priority queues, the entries of these lists will be pairs of the form $(p, o)$, where $p$ is the priority of the object $o$. Usually, the priorities are numbers and, contra-intuitively, high priorities correspond to small numbers, that is $(p_1, o_1)$ has a higher priority than $(p_2, o_2)$ iff $p_1 < p_2$.

We need only two functions from the module heapq:

Given a heap $H$, the function $\texttt{heapq.heappop}(H)$ removes the pair from H that has the highest priority. This pair is also returned.
Given a heap $H$, the function $\texttt{heapq.heappush}\bigl(H, (p, o)\bigr)$ pushes the pair $(p, o)$ onto the heap $H$. This method does not return a value. Instead, the heap $H$ is changed in place.



In [ ]:

    
import heapq

The function search takes three arguments to solve a search problem:

start is the start state of the search problem,
goalis the goal state, and
next_states is a function with signature $\texttt{next_states}:Q \rightarrow 2^Q$, where $Q$ is the set of states. For every state $s \in Q$, $\texttt{next_states}(s)$ is the set of states that can be reached from $s$ in one step.
heuristic is a function that takes two states as arguments. It returns an estimate of the length of the shortest path between these states. If successful, search returns a path from start to goal that is a solution of the search problem $$ \langle Q, \texttt{next_states}, \texttt{start}, \texttt{goal} \rangle. $$

The variable PrioQueue that is used in the implementation contains pairs of the form $$ \bigl(\texttt{heuristic}(\texttt{state}, \texttt{goal}), \texttt{Path}\bigr), $$ where Path is a path from start to state and $\texttt{heuristic}(\texttt{state}, \texttt{goal})$ is an estimate of the distance from state to goal. The idea is to always extend the most promising Path, i.e. to extend the Path, whose last state is closest to goal.



In [ ]:

    
def search(start, goal, next_states, heuristic):
    PrioQueue = [ (heuristic(start, goal), [start]) ]
    while len(PrioQueue) > 0:
        _, Path = heapq.heappop(PrioQueue)
        state   = Path[-1]
        if state == goal:
            return Path
        for ns in next_states(state):
            if ns not in Path:
                d = heuristic(ns, goal)
                heapq.heappush(PrioQueue, (d, Path + [ns]))



In [ ]:

    
%run Sliding-Puzzle.ipynb



In [ ]:

    
%%time
Path = search(start, goal, next_states, manhattan)
print(len(Path)-1)



In [ ]:

    
animation(Path)



In [ ]:

    
%%time
Path = search(start2, goal2, next_states, manhattan)
print(len(Path)-1)



In [ ]: